package chujisuanfa;

import java.util.*;

public class MathXiao {


    public int countPrimes(int n) {
        boolean[] isPrimes = new boolean[n];
        Arrays.fill(isPrimes,true);
        int count = 0;
        for(int i =2;i<n;++i){
            if(isPrimes[i]){
                count+=1;
                if((long)i*i<n){
                    for(int j=i*i;j<n;j+=i){
                        isPrimes[j]=false;
                    }
                }
            }

        }
        return count;
    }
    public int romanToInt(String s) {
        int len = s.length();
        int res = 0;
        for(int i = 0;i<len;++i){
           switch (s.charAt(i)) {
               case 'M':
                   res += 1000;
                   break;
               case 'D':
                   res += 500;
                   break;
               case 'C':
                   if (i < len - 1 && s.charAt(i + 1) == 'M') {
                       res += 900;
                       i++;
                   } else if (i < len - 1 && s.charAt(i + 1) == 'D') {
                       res += 400;
                       i++;
                   } else res += 100;
                   break;
               case 'L':
                   res += 50;
                   break;
               case 'X':
                   if (i < len - 1 && s.charAt(i + 1) == 'L') {
                       res += 40;
                       i++;
                   } else if (i < len - 1 && s.charAt(i + 1) == 'C') {
                       res += 90;
                       i++;
                   } else res += 10;
                   break;
               case 'V':
                   res += 5;
                   break;
               case 'I':
                   if (i < len - 1 && s.charAt(i + 1) == 'V') {
                       res += 4;
                       i++;
                   } else if (i < len - 1 && s.charAt(i + 1) == 'X') {
                       res += 9;
                       i++;
                   } else res += 1;
                   break;
           }
        }
        return res;
    }

    //连续子序列
    public int[][] findContinuousSequence(int target) {

        List<int[]> list = new ArrayList<>();

        for(int i=1;i<=target/2;++i){
            List<Integer> arr = new ArrayList<>();
            int sum = 0,k=i;
            while(sum<target){
                sum+=k;
                arr.add(k);
                k++;
            }
            if(sum==target){
                Integer[] a = (Integer[]) arr.toArray();
            }

        }
        return list.toArray(new int[0][]);
    }

    //打印顺时针数组
    public int[] spiralOrder(int[][] matrix) {
        int row = matrix.length;
        if (row==0) return new int[]{};
        int col = matrix[0].length;
        int[] res = new int[row*col];
        int count=0;
        for(int i=0;i<Math.min((row+1)/2,(col+1)/2);i++){
            int j=i;
            while(j<matrix[0].length-i){
                res[count++] = matrix[i][j++];
                if(count==res.length) return res;
            }
            j--;
            int k=i+1;
            while(k<row-i){
                res[count++] = matrix[k++][j];
                if(count==res.length) return res;
            }
            k--;
            j--;
            while(j>=i){
                res[count++] = matrix[k][j--];
                if(count==res.length) return res;
            }
            j++;
            k--;
            while(k>i){
                res[count++] = matrix[k--][j];
                if(count==res.length) return res;
            }
        }
        return res;
    }


    //判断栈顺序
    public boolean validateStackSequences(int[] pushed, int[] popped) {

        Stack<Integer> stack  =new Stack<>();
        int count =0;
        for (int i : pushed){
            stack.push(i);
            while (!stack.isEmpty()){
                if(popped[count++]==stack.peek()) stack.pop();
            }
        }
        return stack.isEmpty();
    }




    public static void main(String[] args) {
        MathXiao m = new MathXiao();
//        System.out.println(m.countPrimes(5000000));
//        System.out.println(m.romanToInt("MCMXCIV"));

//        System.out.println(m.maxSlidingWindow(new int[]{1,3,5,2,6,4,7},3));
    }
}
